public class sort {
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length ; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if(tmp < array[j]) {
                    array[j + 1] = array[j ];
                } else {
                     array[j+1] = tmp;
                     break;
                }
            }
            array[j+1] = tmp;

        }
    }
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int midIndex =  i;
            int j = i+1;
            for (; j < array.length ; j++) {
                if(array[j] < array[midIndex]) {
                    midIndex = j;
                }
            }
            //swap
            swap(array,i,midIndex);
        }
    }
    public static void swap(int[] array,int p ,int q ) {
        int tmp = array[p];
        array[p] = array[q];
        array[q] = tmp;
    }
    public static void selectSort2(int[] array) {
        int left = 0 ;
        int right = array.length -1;
        while(left < right) {
            int minIndex = left ;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            if(left == maxIndex) {
                maxIndex = right;
            }
            swap(array,left,minIndex);
            swap(array,right,maxIndex);
            left++;
            right--;
        }

    }
}
